package com.waitingresult.common;

import java.util.Scanner;

/**
 * @Author: WangShuai
 * @CreateTime: 2023-02-28  17:52
 * @Description:
 * @Version: 1.0
 */
public class DfsForCDemo {
        public static void main(String[] args) {
        permutations(new String[]{"A","B","C","D"});
    }
    //初始化，n记得在外面初始化啊，要不然dfs里调不到
    public static int N = 10, n;
    public static String[] path = new String[N];
    public static boolean[] st = new boolean[N];

    public static void permutations(String[] list) {
        //初始化
        n = list.length;
        dfs(0,list);
    }

    //这里的核心思想就是找到未被使用的数，例如第一个数为1，那么第二个数只能为2或者3，第二个数为2，第三个数就只能为3，以此类推
    //用st，boolean数组标记当前数字有没有被使用过
    //path数组记录下当前这一串数，最后当u==n说明没有数可用了，探底了，就输出path的内容
    //path不用每次清空，因为每次path都会被覆盖
    public static void dfs(int u,String[] list) {
        if (u == n) {
            for (int i = 0; i < n; i++) {
                System.out.print(path[i] + " ");
                // System.out.print(list[i] + " ");

            }
            System.out.println();
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (!st[i]) {
                path[u] = list[i-1];
                st[i] = true;
                dfs(u + 1,list);
                st[i] = false;
            }
        }
    }
}
